package com.xiaoyg.algorithm;

/***
 * 素数计算
 */
public class PrimeNumber{

    public static void main(String[] args) {
//        System.out.println(violentSolution(100));
        System.out.println(eratorsthenes(100));
    }


    public static int violentSolution(int num){
        int count = 0;
        for (int i = 0; i < num; i++) {
            if (isPrime(i)){
                count += 1;
            }
        }
        return count;
    }

    private static boolean isPrime(int i) {
        if (i <= 1){
            return false;
        }
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0){
                return false;
            }
        }
        return true;
    }
    
    public static int eratorsthenes(int n){
        boolean [] isPrime = new boolean[n]; //false代表素数
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]){
                count ++;
                for (int j = i * i; j < n; j+= i) { //j代表合数的下标
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }
}
